/*
 * Copyright (C) 2009,2010,2011  Paulo Cesar Pereira de Andrade.
 *
 * This is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This software is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * Authors:
 *	Paulo Cesar Pereira de Andrade
 */

#include "exl.h"

#define rdc_mone		1
#define rdc_zero		2
#define rdc_one			4
#define rdc_inv			8
#define rdc_int			16
#define rdc_float		32
#define rdc_complex		64
#define rdc_vector		128
#define rdc_record		256
#define rdc_symbol		512

/*
 * Prototypes
 */
static ebool_t
reduce_binary(east_list_t *list, east_node_t *node,
	      east_list_t *prev_arg0, east_node_t *arg0,
	      east_list_t *prev_push,
	      east_list_t *list_arg1, east_node_t *arg1);

static ebool_t
reduce_incdec_complex(east_list_t *prev);

static ebool_t
reduce_incdec(east_list_t *prev);

static void
reduce_incdec_vector(east_list_t *list);

static void
reduce_incdec_record(east_list_t *list);

static void
reduce_incdec_hash(east_list_t *list);

static ebool_t
reduce_bool(ecode_t code, east_list_t *prev);

static eint32_t
reduce_state(east_node_t *node);

static east_node_t *
reduce_invert(east_node_t *node);

/*
 * Initialization
 */
static ebool_t		again;

/*
 * Implementation
 */
ebool_t
ereduce(efunction_t *function)
{
    east_node_t		*arg0;
    east_node_t		*arg1;
    east_list_t		*list;
    east_node_t		*node;
    east_list_t		*prev;
    eint32_t		 state;
    east_list_t		*prev_arg0;
    east_list_t		*prev_push;
    east_list_t		*list_arg1;

    v_check(1);

#define have_none	0
#define have_arg0	1
#define wait_arg1	2
#define have_arg1	4
    cfg_note = null;
    state = have_none;
    arg0 = arg1 = null;
    prev_arg0 = prev_push = list_arg1 = null;
    prev = function->code;
    for (list = east_next(prev); list; prev = list, list = east_next(list)) {
	node = east_node(list);
	switch (node->code) {
	    case eop_nil:			case eop_int:
	    case eop_float:			case eop_ll:
	    case eop_ld:			case eop_ldt:
	    case eop_lb:			case eop_lbt:
	    case eop_lc:			case eop_ls:
	    case eop_lvai:
		if (state == wait_arg1) {
		    arg1 = node;
		    list_arg1 = list;
		    state = have_arg1;
		}
		else {
		    arg0 = node;
		    prev_arg0 = prev;
		    state = have_arg0;
		}
		break;
	    case eop_push:
		if (node->cstack.flags & code_stack_binarg) {
		    if (state != have_arg0) {
			arg0 = null;
			/* just to avoid needing to check if arg0 is null */
			prev_arg0 = prev;
		    }
		    prev_push = prev;
		    state = wait_arg1;
		}
		else {
		    if (node->cstack.flags & code_stack_incdec_complex &&
			reduce_incdec_complex(prev))
			list = prev;
		    state = have_none;
		}
		break;
	    case eop_pushv:
		if (state == have_arg0 &&
		    node->cstack.flags & code_stack_incdec &&
		    reduce_incdec(prev))
		    list = prev;
		state = have_none;
		break;
	    case eop_lvref:
		if (node->cvector.arg == 1)
		    reduce_incdec_vector(list);
		state = have_none;
		break;
	    case eop_lrref:
		if (node->crecord.arg == 1)
		    reduce_incdec_record(list);
		state = have_none;
		break;
	    case eop_lhref:
		if (node->chash.arg == 1)
		    reduce_incdec_hash(list);
		state = have_none;
		break;
	    case eop_not:			case eop_bool:
		if (reduce_bool(node->code, prev))
		    list = prev_arg0;
		state = have_none;
		break;
	    case eop_eq:			case eop_ne:
	    case eop_and:			case eop_or:
	    case eop_xor:			case eop_add:
	    case eop_sub:			case eop_mul:
	    case eop_div:			case eop_trunc2:
	    case eop_mul2:			case eop_div2:
	    case eop_shl:			case eop_shr:
		if (state == have_arg1 &&
		    reduce_binary(list, node,
				  prev_arg0, arg0,
				  prev_push,
				  list_arg1, arg1))
		    list = prev_arg0;
		state = have_none;
		break;
	    case eop_j:
		/* basic block may end in an orphan load
		 * after basic jump optimization */
		if (state == have_arg0 &&
		    !ecfg_implicit_used_p(east_next(elabel_list(node->clabel.label)))) {
		    east_next(prev_arg0) = list;
		    list = prev_arg0;
		    again = true;
		}
		state = have_none;
		break;
	    case eop_note:
		cfg_note = node;
		break;
	    default:
		state = have_none;
		break;
	}
    }

    return (again);
}

static ebool_t
reduce_binary(east_list_t *list,      east_node_t *node,
	      east_list_t *prev_arg0, east_node_t *arg0,
	      east_list_t *prev_push,
	      east_list_t *list_arg1, east_node_t *arg1)
{
    eint32_t	state0;
    eint32_t	state1;

    state0 = reduce_state(arg0);
    state1 = reduce_state(arg1);

#define arg1_unary__return(unary_code)					\
    do {								\
	east_next(prev_arg0) = list_arg1;				\
	node->code = unary_code;					\
	return (again = true);						\
    } while (0)
#define arg0_unary__return(unary_code)					\
    do {								\
	east_next(prev_push) = list;					\
	node->code = unary_code;					\
	return (again = true);						\
    } while (0)
    switch (node->code) {
	case eop_eq:
	    if (state0 & rdc_zero)		/* 0 == v => !v */
		arg1_unary__return(eop_not);
	    if (state1 & rdc_zero)		/* v == 0 => !v */
		arg0_unary__return(eop_not);
	    break;
	case eop_ne:
	    if (state0 & rdc_zero)		/* 0 != v => !!v */
		arg1_unary__return(eop_bool);
	    if (state1 & rdc_zero)		/* v != 0 => !!v */
		arg0_unary__return(eop_bool);
	    break;
	case eop_and:
	    if (!(state0 & (rdc_int|rdc_vector|rdc_symbol)) ||
		!(state1 & (rdc_int|rdc_vector|rdc_symbol)))
		ecfg_error(parse, "not an integer");
	    if (state0 & rdc_zero)		/* 0 & v => int_p(v), 0 */
		arg1_unary__return(eop_intp_0);
	    if (state1 & rdc_zero)		/* v & 0 => int_p(v), 0 */
		arg0_unary__return(eop_intp_0);
	    if (state0 & rdc_mone)		/* v & -1 => int_p(v), v */
		arg1_unary__return(eop_intp_v);
	    if (state1 & rdc_mone)		/* -1 & v => int_p(v), v */
		arg0_unary__return(eop_intp_v);
	    break;
	case eop_or:
	    if (!(state0 & (rdc_int|rdc_vector|rdc_symbol)) ||
		!(state1 & (rdc_int|rdc_vector|rdc_symbol)))
		ecfg_error(parse, "not an integer");
	    if (state0 & rdc_zero)		/* 0 | v => int_p(v), v */
		arg1_unary__return(eop_intp_v);
	    if (state1 & rdc_zero)		/* v | 0 => int_p(v), v */
		arg0_unary__return(eop_intp_v);
	    if (state0 & rdc_mone)		/* -1 | v => int_p(v), -1 */
		arg1_unary__return(eop_intp_n1);
	    if (state1 & rdc_mone)		/* v | -1 => int_p(v), -1 */
		arg0_unary__return(eop_intp_n1);
	    break;
	case eop_xor:
	    if (!(state0 & (rdc_int|rdc_vector|rdc_symbol)) ||
		!(state1 & (rdc_int|rdc_vector|rdc_symbol)))
		ecfg_error(parse, "not an integer");
	    if (state0 & rdc_zero)		/* 0 ^ v => int_p(v), v */
		arg1_unary__return(eop_intp_v);
	    if (state1 & rdc_zero)		/* v ^ 0 => int_p(v), v */
		arg0_unary__return(eop_intp_v);
	    if (state0 & rdc_mone)		/* -1 ^ v => ~v */
		arg1_unary__return(eop_com);
	    if (state1 & rdc_mone)		/* v ^ -1 => ~v */
		arg0_unary__return(eop_com);
	    break;
	case eop_add:
	    if ((state0 & rdc_float) || (state1 & rdc_float))
		return (false);
	    if (state0 & rdc_zero)		/* 0 + v => num_p(v), v */
		arg1_unary__return(eop_nump_v);
	    if (state1 & rdc_zero)		/* v + 0 => num_p(v), v */
		arg0_unary__return(eop_nump_v);
	    if (state0 & rdc_one)		/* 1 + v => ++valueof(v) */
		arg1_unary__return(eop_inc);
	    if (state1 & rdc_one)		/* v + 1 => ++valueof(v) */
		arg0_unary__return(eop_inc);
	    if (state0 & rdc_mone)		/* -1 + v => --valueof(v) */
		arg1_unary__return(eop_dec);
	    if (state1 & rdc_mone)		/* v + -1 => --valueof(v) */
		arg0_unary__return(eop_dec);
	    break;
	case eop_sub:
	    if ((state0 & rdc_float) || (state1 & rdc_float))
		return (false);
	    if (state0 & rdc_zero)		/* 0 - v => -v */
		arg1_unary__return(eop_neg);
	    if (state1 & rdc_zero)		/* v - 0 => num_p(v), v */
		arg0_unary__return(eop_nump_v);
	    if (state1 & rdc_one)		/* v - 1 => --valueof(v) */
		arg0_unary__return(eop_dec);
	    if (state1 & rdc_mone)		/* v - -1 => ++valueof(v) */
		arg0_unary__return(eop_inc);
	    break;
	case eop_mul:
	    if ((state0 & rdc_float) || (state1 & rdc_float))
		return (false);
	    if (state0 & rdc_zero)		/* 0 * v => num_p(v), 0 */
		arg1_unary__return(eop_nump_0);
	    if (state1 & rdc_zero)		/* v * 0 => num_p(v), 0 */
		arg0_unary__return(eop_nump_0);
	    if (state0 & rdc_one)		/* 1 * v => num_p(v), v */
		arg1_unary__return(eop_nump_v);
	    if (state1 & rdc_one)		/* v * 1 => num_p(v), v */
		arg0_unary__return(eop_nump_v);
	    if (state0 & rdc_mone)		/* -1 * v => -v */
		arg1_unary__return(eop_neg);
	    if (state1 & rdc_mone)		/* v * -1 => -v */
		arg0_unary__return(eop_neg);
	    if (state0 & rdc_inv) {		/* 1/# * v => v / # */
#if 1
		/* don't change nodes and reorder list without the need
		 * of a prev pointer; this only works for non sequence
		 * arguments, and this code should be run when arg1 is
		 * a symbol, and allow having a pointer to list_arg1
		 * elsewhere (meant for faster/simpler propagation,
		 * until optimization of sequences (re)added) */
		east_list_t		*list_push;

		list_push = east_next(prev_push);
		east_node(prev_push) = reduce_invert(arg0);
		east_next(prev_arg0) = list_arg1;
		east_next(list_arg1) = list_push;
		east_next(list_push) = prev_push;
		east_next(prev_push) = list;
#else
		east_node(east_next(prev_arg0)) = arg1;
		east_node(list_arg1) = reduce_invert(arg0);
#endif
		node->code = eop_div;
	    }
	    if (state1 & rdc_inv) {		/* v * 1/# => v / # */
		east_node(list_arg1) = reduce_invert(arg1);
		node->code = eop_div;
	    }
	    break;
	case eop_div:
	    if ((state0 & rdc_float) || (state1 & rdc_float))
		return (false);
	    if (state0 & rdc_one)		/* 1 / v => inv(v) */
		arg1_unary__return(eop_inv);
	    if (state1 & rdc_one)		/* v / 1 => num_p(v), v */
		arg0_unary__return(eop_nump_v);
	    if (state1 & rdc_mone)		/* v / -1 => -v */
		arg0_unary__return(eop_neg);
	    if (state1 & rdc_inv) {		/* v / 1/# => v * # */
		east_node(list_arg1) = reduce_invert(arg1);
		node->code = eop_mul;
	    }
	    break;
	case eop_trunc2:
	    if (state1 & rdc_one)		/* v \ 1 => trunc(v) */
		arg0_unary__return(eop_trunc);
	    break;
	case eop_mul2:				case eop_div2:
	    if (state1 & rdc_zero)		/* v << 0 => num_p(v), v */
		arg0_unary__return(eop_nump_v);	/* v >> 0 => num_p(v), v */
	    break;
	case eop_shl:				case eop_shr:
	    if (state1 & rdc_zero)		/* v <<< 0 => floor(v) */
		arg0_unary__return(eop_floor);	/* v >>> 0 => floor(v) */
	    break;
	default:
	    abort();
    }
    return (false);
}

static ebool_t
reduce_incdec_complex(east_list_t *prev)
{
    east_list_t		*base;
    east_node_t		*node;
    east_list_t		*list;
    east_list_t		*post;
    east_list_t		*tail;

    /* <prev> push |push| load ssv-2 code store pop <next> */
    list = east_next(east_next(prev));		assert(list != null);

    if (east_node(list)->code != eop_push)
	return (false);

    /* <prev> push BASE=|push| load ssv-2 code store pop <next> */
    base = list;

    /* <prev> push BASE=push |load| ssv-2 code store pop <next> */
    list = east_next(list);			assert(list != null);

    switch (east_node(list)->code) {
	case eop_lva:				case eop_lref:
	    break;
	default:
	    return (false);
    }

    /* <prev> push BASE=push POST=|load| ssv-2 code store pop <next> */
    post = list;

    /* <prev> push BASE=push POST=load |ssv-2| code store pop <next> */
    list = east_next(list);			assert(list != null);

    node = east_node(list);
    if (node->code != eop_ssv || node->cstack.offset != -2)
	return (false);

    /* <prev> push BASE=push POST=load ssv-2 |code| store pop <next> */
    list = east_next(list);			assert(list != null);
    switch (east_node(list)->code) {
	case eop_inc:				case eop_dec:
	    break;
	default:
	    return (false);
    }

    /* <prev> push BASE=push POST=load ssv-2 code |store| pop <next> */
    list = east_next(list);			assert(list != null);
    switch (east_node(list)->code) {
	case eop_sva:				case eop_sref:
	    break;
	default:
	    return (false);
    }

    /* <prev> push BASE=push POST=load ssv-2 code TAIL=|store| pop <next> */
    tail = list;

    /* <prev> push BASE=push POST=load ssv-2 code TAIL=store |pop| <next> */
    if ((list = east_next(list)) == null ||
	east_node(list)->code != eop_pop ||
	ecfg_implicit_used_p(east_next(list)))
	return (false);

    /* convert post incdec to incdec */

    /* <prev> BASE=push POST=load ssv-2 code TAIL=store |pop| <next> */
    east_next(prev) = base;

    /* <prev> BASE=push POST=load code TAIL=store |pop| <next> */
    east_next(post) = east_next(east_next(post));

    /* <prev> BASE=push POST=load code TAIL=store <next> */
    east_next(tail) = east_next(list);

    return (true);
}

static ebool_t
reduce_incdec(east_list_t *prev)
{
    east_list_t		*base;
    east_list_t		*list;
    east_list_t		*tail;

    /* <prev> push |code| store pop <next> */
    list = east_next(east_next(prev));		assert(list != null);

    /* <prev> push BASE=|code| store pop <next> */
    base = list;

    switch (east_node(list)->code) {
	case eop_inc:				case eop_dec:
	    break;
	default:
	    return (false);
    }

    /* <prev> push BASE=code |store| pop <next> */
    list = east_next(list);			assert(list != null);
    switch (east_node(list)->code) {
	case eop_sd:				case eop_sdt:
	case eop_sb:				case eop_sbt:
	case eop_sc:				case eop_svai:

	    /* <prev> push BASE=code TAIL=|store| pop <next> */
	    tail = list;

	    /* <prev> push BASE=code TAIL=store |pop| <next> */
	    if ((list = east_next(list)) == null ||
		east_node(list)->code != eop_pop ||
		ecfg_implicit_used_p(east_next(list)))
		return (false);

	    /* convert post incdec to incdec */

	    /* <prev> BASE=code TAIL=store |pop| <next> */
	    east_next(prev) = base;

	    /* <prev> BASE=code TAIL=store <next> */
	    east_next(tail) = east_next(list);

	    return (true);
	default:
	    return (false);
    }
}

static void
reduce_incdec_vector(east_list_t *list)
{
    east_node_t		*base;
    east_node_t		*tail;

    base = east_node(list);
    list = east_next(list);
    assert(list != null);
    switch (east_node(list)->code) {
	case eop_inc:				case eop_dec:
	    break;
	default:
	    return;
    }
    list = east_next(list);
    tail = east_node(list);
    assert(tail->code == eop_svref && tail->cvector.arg == 1);
    if (!ecfg_implicit_used_p(east_next(list)))
	base->cvector.arg = tail->cvector.arg = 0;
}

static void
reduce_incdec_record(east_list_t *list)
{
    east_node_t		*base;
    east_node_t		*tail;

    base = east_node(list);
    list = east_next(list);
    assert(list != null);
    switch (east_node(list)->code) {
	case eop_inc:				case eop_dec:
	    break;
	default:
	    return;
    }
    list = east_next(list);
    tail = east_node(list);
    assert(tail->code == eop_srref && tail->crecord.arg == 1);
    if (!ecfg_implicit_used_p(east_next(list)))
	base->crecord.arg = tail->crecord.arg = 0;
}

static void
reduce_incdec_hash(east_list_t *list)
{
    east_node_t		*base;
    east_node_t		*tail;

    base = east_node(list);
    list = east_next(list);
    assert(list != null);
    switch (east_node(list)->code) {
	case eop_inc:				case eop_dec:
	    break;
	default:
	    return;
    }
    list = east_next(list);
    tail = east_node(list);
    assert(tail->code == eop_shref && tail->chash.arg == 1);
    if (!ecfg_implicit_used_p(east_next(list)))
	base->chash.arg = tail->chash.arg = 0;
}

static ebool_t
reduce_bool(ecode_t code, east_list_t *prev)
{
    east_list_t		*list;
    east_node_t		*node;
    elabel_t		*label;

    for (list = east_next(east_next(prev)); list; list = east_next(list)) {
	node = east_node(list);
	switch (node->code) {
	    case eop_jt:			case eop_jf:
		label = node->clabel.label;
		if (/* code after jump uses computed value */
		    ecfg_implicit_used_p(east_next(list)) ||
		    /* code after jump target uses computed value */
		    ecfg_implicit_used_p(east_next(elabel_list(label))))
		    return (false);
		/* exp, not, jt => exp, jf */
		/* exp, bool, jt => exp, jt */
		if (code == eop_not)
		    node->code = node->code == eop_jt ? eop_jf : eop_jt;
		east_next(prev) = list;
		return (again = true);
		break;
	    case eop_note:
		break;
	    default:
		return (false);
	}
    }
    return (false);
}

static eint32_t
reduce_state(east_node_t *node)
{
    eint32_t	type;
    eobject_t	value;

    if (node == null)
	return (rdc_symbol);

    switch (node->code) {
	case eop_nil:
	    return (rdc_int|rdc_zero);
	case eop_int:
	    if (immediate_int(node) == 0)
		return (rdc_int|rdc_zero);
	    if (immediate_int(node) == 1)
		return (rdc_int|rdc_one);
	    if (immediate_int(node) == -1)
		return (rdc_int|rdc_mone);
	    return (rdc_int);
	case eop_float:
	    if (immediate_float(node) == 0.0/* &&
		!signbit(immediate_float(node))*/)
		return (rdc_float|rdc_zero);
	    return (rdc_float);
	case eop_ll:
	    value = els[immediate_offset(node)];
	    switch (type = etype(value)) {
		case t_mpz:
		    return (rdc_int);
		case t_mpq:
		    if (mpz_cmpabs_ui(mpq_numref((empq_t)value), 1) == 0)
			return (rdc_inv);
		    return (0);
		case t_mpr:
		    if (mpfr_zero_p((empr_t)value))
			return (rdc_float|rdc_zero);
		    return (rdc_float);
		case t_cdd:
		case t_cqq:
		case t_mpc:
		    return (rdc_complex);
		default:
		    return (evector_type_p(type) ? rdc_vector : rdc_record);
	    }
	    break;
	default:
	    return (rdc_symbol);
    }
}

static east_node_t *
reduce_invert(east_node_t *node)
{
    empq_t	mpq;
    empz_t	mpz;

    assert(node->code == eop_ll);
    mpq = els[immediate_offset(node)];
    assert(etype(mpq) == t_mpq);

    mpz = thr_zr;
    mpz_set(mpz, mpq_denref(mpq));
    if (mpz_sgn(mpq_numref(mpq)) < 0)
	mpz_neg(mpz, mpz);
    if (empz_fit_i(mpz))
	return (ecode_int(empz_get_i(mpz)));
    enew_mpz((eobject_t *)&mpz, mpz);
    v_push(mpz);
    node = ecode_literal(econstant(mpz));
    v_dec();

    return (node);
}
